Shingle
Abstract class for string similarities that rely on set operations (like cosine similarity or jaccard index).
k-shingling is the operation of transforming a string (or text document) into a set of n-grams, which can be used to measure the similarity between two strings or documents.
Generally speaking, a k-gram is any sequence of k tokens. We use here the definition from Leskovec, Rajaraman & Ullman (2014), "Mining of Massive Datasets", Cambridge University Press: Multiple subsequent spaces are replaced by a single space, and a k-gram is a sequence of k characters.
Default value of k is 3. A good rule of thumb is to imagine that there are only 20 characters and estimate the number of k-shingles as \(20^k\). For small documents like e-mails, \(k = 5\) is a recommended value. For large documents, such as research articles, \(k = 9\) is considered a safe choice.
References
Ukkonen, E. (1992-01). Approximate string matching with q-grams and maximal matches. Theoretical Computer Science, 92(1), 191–211. https://doi.org/10.1016/0304-3975(92)90143-4[sci-hub]
Author
Thibault Debatty, solonovamax
Parameters
The length of k-shingles.
Throws
if \(k \leqslant 0\)
Inheritors
Functions
Compute and return the profile of s, as defined by Ukkonen (Ukkonen 1992). The profile is the number of occurrences of k-shingles, and is used to compute q-gram similarity, Jaccard index, etc. Pay attention: the memory requirement of the profile can be up to \(k \times \text{size of the string}\)